FIG. 1 shows various devices that a user may own and use. These devices include, but are not limited to, a computer 100, a portable device 110, a personal digital assistant 120, a cellular phone (not shown), etc. The user may have several such devices that store various forms of information, such as contacts, calendar dates, documents, notes, etc. In using these devices, the user may synchronize a set of information stored on one device with the same set of information stored on another device. As expected, this synchronization process seeks to maintain consistency between the sets of information.
For example, the desktop computer 100 may have personal information management (“PIM”) data (e.g., contacts, calendar dates, etc.). At some point, the user of that desktop computer 100 may want to use that PIM data when she is away from her desktop computer 100, and she may want to access the PIM data while using her portable device 110 or PDA 120. To provide that ability, her portable device 110 and PDA 120 may each carry their own copies of the PIM data that correspond to the PIM data on the desktop computer 100. Because each of these devices 100, 110, and 120 could potentially have different copies (versions) of the same PIM data that have been added, changed, updated, etc. at different times and in different ways, it may be necessary for the user to synchronize the PIM data between devices so the user can have a common view of her PIM data on each device.
A common technique for synchronizing devices uses snapshots of data at a point-in-time and compares current data to the snapshot to determine what has changed. For example, the computer 100 may have a database 102 that stores the current PIM data edited or added on the computer 100. The computer 100 may also have a snapshot database 104 that is a snapshot of the PIM data taken at some previous point-in-time. Typically, the previous point-in-time is when a prior or most recent synchronization took place. Similarly, the portable device 110 has a database 112 for current PIM data. Having these structures in place, the user may attempt to synchronize the computer 100 and the portable device 110. The typical synchronization technique compares both the portable's database 112 and the computer's database 102 with the snapshot database 104 on the computer 100. During the compare operation, the synchronization technique assembles a list of data items that are new or changed in the active databases 102 and 112 as compared to the snapshot database 104. Finally, to finish out the synchronization, the synchronization technique uses the list of new and changed data to update all three databases 102, 104, and 112.
This synchronization technique experiences problems when information is inconsistently changed on both the computer 100 and the portable device 110. For example, before synchronization, the user may have change Jane Doe's phone number on the computer 100 to 877-555-5555 and may have changed Jane Doe's phone number on the portable device 110 to 800-555-5555. During the compare operation of the synchronization, the synchronizing system will notice this discrepancy and identify a conflict. In the current art, there is generally no elegant way to resolve this conflict with certainty. Some synchronization techniques present an interface to the user and ask her to choose between the two pieces of data. Unfortunately, even the user may not remember which piece of data is correct. Other synchronization techniques simply create duplicate entries in each database 102/112 having both possible data items on the two devices 100 and 110.
Problems with conflicting data are exacerbated if there are more than two devices carrying corresponding data sets. In FIG. 1, for example, the computer 100 may be synchronized with the PDA 120 after first synchronizing with the portable device 110. During synchronization, the PDA 120 may carry Jane Doe's phone number as yet a different value of 888-555-555, thus presenting a conflict with the phone number carried in both the computer 100 and the portable device 110. Unfortunately, in the prior art, there is no elegant solution for determining the correct result with certainty. Furthermore, even if the correct result can be determined at the time of synchronization (e.g., by the user, who remembers the correct number), the synchronizing system may simply have the same conflict problem again the next time the portable device 110 is synchronized.
In the above description of FIG. 1, none of the devices has a master database containing all of the up-to-date data items that can then be used as a centralized repository from which to synchronize with all other devices. As such, this form of arrangement represents a peer-to-peer system in a decentralized environment. In general, in such a peer-to-peer system with three or more peers (e.g., devices) where the peers may synchronize with each other two at a time and where there is no centralized repository, there is no way to know whether one of the peers carries more up-to-date data than the other peer.
Notably, a simple timestamp cannot resolve a conflict between data items on the syncing peers with certainty as a matter of practical human usage. If, for example, two corresponding data items have been changed over the past days or months at first and second peers, the time when those changes occurred does not necessarily mean that the “later” time stamped change is correct. This is especially true if the “later” change actually occurred as a result of synchronization with a third peer, which itself may have received its data change long ago. Furthermore, each peer must have the same clock value to make any comparison of timestamps effective.
Therefore, in the decentralized peer-to-peer system merely using time-related information, the synchronization system would be unable to determine whether a detected conflict is a true conflict that must be resolved by the user on the one hand or whether the detected conflict is an apparent conflict that could be verifiably resolved if the system understood the history of the data on the other hand. To understand the history of the data, however, the synchronization system may need to store a great deal of information related to the history of the data, making the synchronization system cumbersome and complex.
In view of the these and other problems existing in the art, what is needed is a synchronization system that is capable of hubless or decentralized syncing in a peer-to-peer system where any number of users and devices can come and go in the system without coordination and where no one device knows the existence of all other devices. What is also needed is a synchronization system that associates lightweight history information with each piece of data and that does not require a universal timestamp or coordinated logical clock common to all peers to perform synchronizations.